package com.xjj.tree;

import com.xjj.TreeNode;

import java.util.*;

public class H0297SerializeAndDeserializeBinaryTree {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        String str = String.join(" ", dfs(root, new ArrayList<>()));
        System.out.println(str);
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> queue = new LinkedList(Arrays.asList(data.split(" ")));
        return buildTree(queue);
    }

    private List<String> dfs(TreeNode root, List<String> list) {
        if (root == null) {
            list.add("null");
            return list;
        }
        list.add(String.valueOf(root.val));
        dfs(root.left, list);
        dfs(root.right, list);
        return list;
    }

    private TreeNode buildTree(Queue<String> queue) {
        if (queue.isEmpty()) {
            return null;
        }
        String str = queue.poll();
        if (str.equals("null")) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(str));
        // 前序dfs构建的,所以也要对应的解码
        node.left = buildTree(queue);
        node.right = buildTree(queue);
        return node;
    }
}
